package com.xzz.tree;

/**
 * @author: hhz
 * @create: 2021-12-17 16:33
 * 105. 从前序与中序遍历序列构造二叉树
 * 给定一棵树的前序遍历 preorder 与中序遍历  inorder。请构造二叉树并返回其根节点。
 **/
public class BuildTree {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        int[] preorder = new int[]{3, 9, 20, 15, 7};
        int[] inorder = new int[]{9,3,15,20,7};
        TreeNode treeNode = buildTree(preorder, inorder);
        System.out.println("根据前序和中序构建二叉树");
        preTraverse(treeNode);
        System.out.println();
        int[] inorder2 = new int[]{9,3,15,20,7};
        int[] postorder  = new int[]{9,15,7,20,3};
        TreeNode node = buildTree2(inorder2, postorder);
        System.out.println("根据中序和后序构建二叉树");
        preTraverse(node);
    }

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }

    public static TreeNode build(int[] preorder, int preStart,int preEnd,
                                 int[] inorder,int inStart,int inEnd) {
        if(preStart > preEnd){
            return null;
        }
        TreeNode root = new TreeNode(preorder[preStart]);
        int index = -1;
        for (int i = inStart; i <= inEnd; i++) {
            if(inorder[i]==root.val){
                index = i;
                break;
            }
        }
        //左子树的size
        int leftSize = index-inStart;
        root.left = build(preorder,preStart+1,preStart+leftSize,
                            inorder,inStart,index-1);
        root.right = build(preorder,preStart+leftSize+1,preEnd,
                            inorder,index+1,inEnd);
        return root;
    }
    public static TreeNode buildTree2(int[] inorder, int[] postorder) {
        return build2(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
    }
    public static TreeNode build2(int[] inorder,int inStart,int inEnd,
                                 int[] postorder,int postStart,int postEnd) {
        if(postStart > postEnd){
            return null;
        }
        TreeNode root = new TreeNode(postorder[postEnd]);
        int index = -1;
        for (int i = inStart; i <= inEnd; i++) {
            if(inorder[i]==root.val){
                index = i;
                break;
            }
        }
        //左子树的size
        int leftSize = index-inStart;
        root.left = build2(inorder,inStart,index-1,
                postorder,postStart,postStart+leftSize-1);
        root.right = build2(inorder,index+1,inEnd,
                    postorder,postStart+leftSize,postEnd-1
                );
        return root;
    }
    public static void preTraverse(TreeNode treeNode){
        if(treeNode!=null){
            System.out.print(treeNode.val+" ");
            preTraverse(treeNode.left);
            preTraverse(treeNode.right);
        }
    }
}
